package leetcode.editor.cn.q1_300.q50;

import java.util.ArrayList;
import java.util.List;

/**
 * @author qidi
 * @date 2021-12-24 10:16:19
 */
class Q0089_GrayCode {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> grayCode(int n) {
            int len = (int) Math.pow(2, n);
            // true 表示已经出现过的数
            boolean[] flags = new boolean[len];
            flags[0] = true;

            int[] num = new int[n];
            List<Integer> result = new ArrayList<>();
            result.add(0);

            int i = 1;
            while (i < len) {
                for (int j = 0; j < n; j++) {
                    int m = num[j];
                    num[j] = m == 0 ? 1 : 0;
                    int nnum = convertNum(num);
                    if (flags[nnum]) {
                        num[j] = m;
                    } else {
                        flags[nnum] = true;
                        result.add(nnum);
                        break;
                    }
                }
                i++;
            }

            return result;
        }

        private int convertNum(int[] arr) {
            int num = 0;
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == 1) num += Math.pow(2, i);
            }
            return num;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0089_GrayCode().new Solution();
        for (int i = 1; i <= 5; i++) {
            System.out.println(i);
            List<Integer> list = solution.grayCode(i);
            System.out.println(list);
        }
    }
}